package main

import "fmt"

type LRUNode struct {
	key   int
	value int
	prv   *LRUNode
	next  *LRUNode
}

type LRUCache struct {
	capacity int
	cache    map[int]*LRUNode
	head     *LRUNode
	tail     *LRUNode
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*LRUNode, 0),
		head:     nil,
		tail:     nil,
	}
}

func (lru *LRUCache) MoveToFront(node *LRUNode) {
	//如果在第一位
	if lru.head == node {
		return
	}
	//如果前面有元素,就让前一个元素的后面的指针链接到后面元素上
	if node.prv != nil {
		node.prv.next = node.next
	}
	//如果后面有元素
	if node.next != nil {
		node.next.prv = node.prv
	}
	//如果在最尾部
	if node == lru.tail {
		lru.tail = node.prv
	}
	//然后把这个元素整到第一位
	node.prv = nil
	node.next = lru.head
	//如果头部元素不为空,就把原本头部的前指针链接到node
	if lru.head != nil {
		lru.head.prv = node
	}
	lru.head = node
	if lru.tail == nil {
		lru.tail = lru.head
	}
}

func (lru *LRUCache) RemoveTail() {
	if lru.tail == nil {
		return
	}
	delete(lru.cache, lru.tail.key)
	if lru.tail == lru.head {
		lru.tail = nil
		lru.head = nil
	} else {
		lru.tail.prv.next = nil
		lru.tail = lru.tail.prv
	}
}

func (lru *LRUCache) Get(key int) int {
	if node, ok := lru.cache[key]; ok {
		lru.MoveToFront(node)
		return node.value
	}
	return -1
}

func (lru *LRUCache) Put(key, value int) {
	if node, ok := lru.cache[key]; ok {
		node.value = value
		lru.MoveToFront(node)
	} else {
		if len(lru.cache) >= lru.capacity {
			lru.RemoveTail()
		}
		newNode := &LRUNode{
			key:   key,
			value: value,
			prv:   nil,
			next:  lru.head,
		}
		if lru.head != nil {
			lru.head.prv = newNode
		}
		lru.head = newNode
		if lru.tail == nil {
			lru.tail = lru.head
		}
		lru.cache[key] = newNode
	}

}
func main() {
	cache := Constructor(2)

	cache.Put(1, 1)           //1
	cache.Put(2, 2)           //2,1
	fmt.Println(cache.Get(1)) // 输出 1 1,2

	cache.Put(3, 3)           //3,1
	fmt.Println(cache.Get(2)) // 输出 -1，因为键 2 不在缓存中
	cache.Put(4, 4)
	fmt.Println(cache.Get(1)) // 输出 -1，因为键 1 已经过期
	fmt.Println(cache.Get(3)) // 输出 3
	fmt.Println(cache.Get(4)) // 输出 4
}
